#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

// 思路： 电话号码的每个数字对应多个字母，我们可以使用深度优先搜索（DFS）来生成所有可能的字母组合。
// 对于每个数字，我们遍历其对应的字母，并将其添加到当前组合中，然后递归处理下一个数字。
// 当我们处理完所有数字时，将当前组合添加到结果集中。
class Solution
{
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> res;
        if (digits.size() == 0)
            return res;
        string temp;
        unordered_map<char, string> u_map{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}};
        dfs(res, digits, 0, temp, u_map);
        return res;
    }
    void dfs(vector<string> &res, string &digits, int index, string &temp, unordered_map<char, string> &u_map)
    {
        if (index == digits.length()) // 到达叶子节点
        {
            res.push_back(temp);
            return;
        }
        for (auto c : u_map[digits[index]]) // 遍历当前数字对应的字母
        {
            temp.push_back(c);                        // 选择当前字母
            dfs(res, digits, index + 1, temp, u_map); // 继续递归处理下一个数字
            temp.pop_back();                          // 回溯，移除最后一个字母
        }
    }
};